package class06;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @description: https://leetcode.com/problems/merge-k-sorted-lists/
 * @time: 2021/7/15 18:43
 * @author: lhy
 */
public class MergeKSortedLists {
    public static class ListNode {
        public int val;
        public ListNode next;
    }
    public static class MyComparator implements Comparator<ListNode>{
        @Override
        public int compare(ListNode o1,ListNode o2){
            return o1.val - o2.val;
        }
    }

    /**
     * 利用最小堆实现
     * 先将所有链表的头结点入堆；
     * 然后弹出最小的一个，如果弹出的结点的next不空，继续入堆
     * 周而复始，直至堆为空，最后返回head
     * @param lists 链表的集合
     * @return head
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new MyComparator());
        for (ListNode list : lists) {
            if (list != null) {
                heap.add(list);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null){
            heap.add(pre.next);
        }
        while (!heap.isEmpty()){
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = pre.next;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }
}
